\section{Concluding remarks and open questions}
We studied the fundamental $k$-gossip problem in dynamic networks and
showed a lower bound of $\Omega(n + nk/\log n)$ rounds for any online
token forwarding algorithm against a strong adversary, significantly
improving over the previous best bound of $\Omega(n\log
k)$~\cite{kuhn+lo:dynamic} for sufficiently large $k$.  Our lower
bound matches the known upper bound of $O(nk)$ up to a logarithmic
factor, and establishes a near-linear factor separation between
token-forwarding and network-coding based algorithms.  While our bound
rules out significantly faster algorithms in the online model, we
complement our lower bound by presenting the first subquadratic time
token-forwarding algorithms in the weaker offline model.

Our almost-tight lower bound of $\Omega(n + nk/\log n)$ rounds extends
to randomized algorithms with an adaptive adversary that makes its
decision in each round with knowledge of the randomness of the
algorithm in that round (but without knowledge of future randomness).
An important open problem is the complexity of randomized online
token-forwarding algorithms against an oblivious adversary that is
unaware of the randomness used by the algorithm.  Also, this paper has
focused on the dynamic network model in which each node can broadcast
at most one token per round and the network can change every round.
Subsequent to the announcement of our results~\cite{arxiv}, our lower
bound argument has been extended to the model where multiple tokens
can be broadcast and the dynamic network is required to contain a
stable subgraph for multiple rounds~\cite{personal}.

For the important practical case of small token sizes (e.g., $O(\log
n)$ bits) even the best online gossip algorithm we know based on
network coding takes $O(n^2/\log n)$ rounds~\cite{haeupler+k:dynamic}.
In contrast, we show that in the offline setting there exist
centralized token-forwarding algorithms that run in
$O(n^{1.5}\sqrt{\log n})$ time.  What is the best possible time
achievable for gossip with small token sizes?

Finally, a major question is whether we can design fully distributed
fast (e.g., $O(\min\{n\sqrt{\log k}, nk\})$ time) token-forwarding
algorithms for general dynamic networks under an offline adversary or,
even better, an oblivious adversary.  We believe that our first
centralized algorithm can be made distributed and will be useful in
resolving this question.

\junk{Finally, in a recent work \cite{rw-podc}, our Algorithm 1 has been
directly adapted to yield a distributed token forwarding algorithm for
information spreading, albeit in a {\em restricted} model of dynamic
networks where it is assumed that the spectral properties of the
networks don't change.  This distributed algorithm has subquadratic
running time only under certain conditions (e.g., the network should
have small dynamic diameter) and is slower in general than the
$O(\min\{n\sqrt{\log k}, nk\})$ round algorithm of this paper.  A
major question is whether we can design fully distributed fast (e.g.,
$O(\min\{n\sqrt{\log k}, nk\})$ time) token-forwarding algorithms for
general dynamic networks under an offline adversary or, even better,
an oblivious adversary.  We believe that the techniques introduced in
this paper will be useful in tackling this question.
}
